package b_sorting_advance.a_merge_sort;

import org.junit.Test;
import utils.ArrayGeneric;
import utils.sorting_helper.SortingHelper;
import utils.sorting_helper.SortingTest;

/**
 * @Author: DeLucia
 * @Description:
 * @Date: 2019/1/22 22:28.
 */
@SuppressWarnings("unchecked")
public class MergeSort extends SortingTest {
    /**
     * 归并排序
     * 平均时间复杂度	最坏时间复杂度	空间复杂度	是否稳定
     * O(nlogn)	    O(nlogn)	O（n）	    是
     *
     * @param arr
     */
    @Override
    public void sort(ArrayGeneric arr) {
        mergeSort(arr, 0, arr.length() - 1); // 递归归并排序
    }

    /**
     * 1 递归归并, 对arr[left..right]的范围进行排序
     *
     * @param arr
     * @param left
     * @param right
     */
    private void mergeSort(ArrayGeneric arr, int left, int right) {
        // 优化点2
        // 因为在数组规模小的时候插入排序更有效
        // 可以当递归到数组长度<16的时候改用插入排序
        //if (left >= right) // 递归结束条件
        //    return;
        if (right - left <= 15) {
            insertionSort(arr, left, right);
            return;
        }
        int mid = (left + right) / 2; // 小心int类型相加后超出int范围导致bug ..
        // 二分法递归 - 分而治之
        mergeSort(arr, left, mid); // left sorted
        mergeSort(arr, mid + 1, right); // right sorted
        // 优化点1:
        // 如果排序后的右边数组的最左的元素大于等于左边数组的最右的元素大时整体就已经是有序的了, 什么也不需要做
        // 反过来说
        // 只有排序后的左边数组的最右的元素比右边数组的最左元素大时需要合并
        if (arr.get(mid).compareTo(arr.get(mid + 1)) > 0) {
            merge(arr, left, mid, right); // merge left and right
        }
    }

    /**
     * 当递归到数组规模小于16的时候
     * 为了提高性能改用插入排序
     * @param arr
     * @param left
     * @param right
     */
    private void insertionSort(ArrayGeneric arr, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            Comparable e = arr.get(i);
            int j;
            for (j = i; j > left && arr.get(j - 1).compareTo(e) > 0; j--) {
                arr.put(j, arr.get(j - 1));
            }
            arr.put(j, e);
        }
    }

    /**
     * 合并arr[left..mid] 和 arr[mid+1..right]
     * 利用辅助数组aux完成
     *
     * @param arr   待排序数组
     * @param left  待排序数组的起始坐标
     * @param mid   待排序数组的中点坐标
     * @param right 待排序数组的结束坐标
     */
    private void merge(ArrayGeneric arr, int left, int mid, int right) {
        // Auxiliary Space -> aux
        ArrayGeneric aux = new ArrayGeneric(right - left + 1);
        // init aux space
        // 把 arr[left,right]复制到新的空间aux[0..right - left]
        for (int i = left; i <= right; i++) {
            aux.put(i - left, arr.get(i));
        }

        // 开始合并左arr[left..mid]右arr[mid+1..right]
        // 临时数组aux起到辅助运算的作用(作为比较和拷贝的数据源, 数据保持不变)
        // 这里需要三个临时指针, 每次比较后向右移动一个位置
        // 原数组arr的左指针 l 对应 辅助空间aux的左指针 l-left
        // 原数组arr的右指针 r 对应 辅助空间aux的右指针 r-left
        // 原数组arr的当前操作位置 c
        // 当c从arr的左侧遍历到右侧, arr 就排序完成了
        int l = left, r = mid + 1;
        for (int c = left; c <= right; c++) {
            if (l > mid) { // 检查 l 的越界问题
                // 如果 l 越过 中点 说明 左空间都合并完成了 接着合并右空间
                arr.put(c, aux.get(r - left));
                r++;
            } else if (r > right) { // 检查 r 的越界问题
                // 如果 r 越过 right 说明 右空间都合并完成了 接着合并左空间
                arr.put(c, aux.get(l - left));
                l++;
            } else if (aux.get(r - left).compareTo(aux.get(l - left)) > 0) {
                // 如果左指针的元素更小那么就替换到源数组的c位置, 同时左指针右移一位
                // 注意左指针可能越过mid导致越界问题
                arr.put(c, aux.get(l - left));
                l++;
            } else {
                // 如果左指针的元素不比右指针的元素更小那么就将右指针的元素替换到源数组的c位置, 同时右指针右移一位
                // 注意右指针可能越过right导致越界问题
                arr.put(c, aux.get(r - left));
                r++;
            }
            // 如果左右指针都走到边界, 整个大循环也正好结束
        }
    }

    @Test
    public void testingSortMethod() {
        ArrayGeneric<Integer> arr = getRandomIntegerArray(2000000, 0, 9);
//        System.out.println(arr);
        long begin = System.currentTimeMillis();
        sort(arr);
        long end = System.currentTimeMillis();
//        System.out.println(arr);
        assert SortingHelper.testSorted(arr);
        System.out.println(end-begin + "ms");
    }
}
